public class Test {
    static int[] tmp;
    public static int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,-1);
    }
    public static int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = (left+right)/2;

        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        int cur1 = left,cur2 = mid+1, i =0;
        while(cur1<=mid && cur2<=right) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            }else {
                ret += mid - cur1 +1;
                tmp[i++] = nums[cur2++];
            }
        }

        while(cur1<=mid) {
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=right) {
            tmp[i++] = nums[cur2++];
        }

        for(int j = left; j<=right; j++) {
            nums[j] = tmp[j-left];
        }

        return ret;
    }
}
